package 堆排序;

public class 更新堆排序 {
	public static void main(String[] args) {
		//分为三步
		//1. 构建大顶堆，在一个三角堆中构建成功
		//2. 针对整个树，从最以后一个非叶子结点开始循环构建堆
		//3. 在完成大顶堆后，交换最顶层结点与最后一个结点，取出最大值
		//3.1 由于破坏结构，然后再次调整大顶堆
		//4. 直到取出所有元素
		
		int tree[] = {2,5,3,1,10,4};
		int n = tree.length;
		heap_sort(tree, n);
		//输出
		for (int i = 0; i < tree.length; i++) {
			System.out.println(tree[i]);
		}
	}
	
	/**
	 * 一次交换
	 * 大顶堆，这种情况只用于子树已经是堆的情况下进行，针对当前一父二子进行排序
	 * @param tree 数组，树
	 * @param n 数组长度，总结点数
	 * @param i 开始结点（父）
	 */
	public static void heapify(int tree[], int n, int i) {
		//出口，i会变，i 每次都会向下，父与子交换，子就是 i，所以会一直减小
		if(i >= n) {
			return ;
		}
		
		//针对i 开始结点，先找到它的两个子结点
		int c1 = 2 * i + 1;
		int c2 = 2 * i + 2;
		//最大值，默认是当前结点（父），--max是下标--
		int max = i;
		//查找最大值，且子结点不超出树的范围
		if(c1 < n && tree[c1] > tree[max]) {
			max = c1;
		}
		if(c2 < n && tree[c2] > tree[max]) {
			max = c2;
		}
		//如果不是当前值最大，那么就交换，然后对后续结点（向下）开始调整
		if(max != i) {
			//交换最大值和当前值，交换之后当前值i 为小，max 为大
			swap(tree, max, i);
			//此时max 不是最大值了，已经是子结点了，向下走，范围变小，它会找到已经变动的那个数
			//开始重新对这个子树重新递归构建大顶堆，因为可能之前子结点很大，但被换到上面之后，这个数就变小了，
			//和它的子结点不匹配了
			heapify(tree, n, max);
		}
	}
	
	/**
	 * 构建堆，有了交换堆的方法，就可以从下向上开始创建堆，从最后一个非叶子结点开始，
	 * 因为从下向上才能保证已经交换过的堆保证是有顺序的，有顺序才能用heapify()方法
	 * @param tree 树
	 * @param n 数组长度
	 */
	public static void build_heap(int tree[], int n) {
		//最后一个结点
		int last_node = n - 1;
		//最后一结点父结点，非叶子结点
		int parent = (last_node - 1) / 2;
		//从最后一个父结点开始交换堆
		for(int i = parent; i >= 0; i--) {
			heapify(tree, n, i);
		}
		//堆构建完成
	}
	
	/**
	 * 堆排序，有了堆，只要每次构建完堆，将根节点（最大值）与最后一个结点交换，然后切断最后一个结点，取出最大值
	 * @param tree 树
	 * @param n 数组长
	 */
	public static void heap_sort(int tree[], int n) {
		//构建堆
		build_heap(tree, n);
		//交换，切断
		for(int i = n - 1; i >= 0; i--) {
			//交换根与最后一个结点
			swap(tree, i, 0);
			//切断，不用减 1 ，直接使用i 最为数组长度，i每次都会自动减
			//交换之后还要重新排序堆，因为堆乱了
			heapify(tree, i, 0);
		}
	}
	
	
	public static void swap(int arr[], int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
}
